package com.zboin.interview150.dynamic;

import java.util.List;

/** Simple
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * 示例 1：
 * 输入：n = 2
 * 输出：2
 * 解释：有两种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶
 * 2. 2 阶
 *
 * 示例 2：
 * 输入：n = 3
 * 输出：3
 * 解释：有三种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶 + 1 阶
 * 2. 1 阶 + 2 阶
 * 3. 2 阶 + 1 阶
 *
 * 提示：
 * 1 <= n <= 45
 */
public class Course70 {

    public static void main(String[] args) {
        List<Result> list = List.of(
                new Result(1, 1),
                new Result(2,2),
                new Result(3, 3),
                new Result(4, 5),
                new Result(5, 8),
                new Result(6, 13)
        );

        Course70 course70 = new Course70();

        list.forEach(item -> {
            int result = course70.climbStairs(item.n);
            System.out.println(item + ", result=" + result + " " + (result == item.expect ? "√" : "X"));
        });
    }

    public int climbStairs(int n) {
        // 对于到达终点的方式，有两种，从上1个台阶移动1步，或者从2个台阶前移动2步
        // 因此可以推出公式：f(n) = f(n-1) + f(n-2)
        // 而对于边界：f(1) = f(0) = 1
        if (n == 1) return 1;
        int d = 1, p = 1, sum = 0;

        for (int i = 2; i <= n; i++) {
            sum = d + p;
            d = p;
            p = sum;
        }

        return sum;

    }

    private static class Result {
        int n;
        int expect;

        public Result(int n, int expect) {
            this.n = n;
            this.expect = expect;
        }

        @Override
        public String toString() {
            return "n=" + n +
                    ", expect=" + expect;
        }
    }
}
